import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.Arrays;
import java.util.stream.Stream;

/**
 * 下一个排列
 * 题目：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * 必须原地修改，只允许使用额外常数空间。
 * <p>
 * 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 * <p>
 * 来源：力扣（LeetCode-31）
 * 链接：https://leetcode-cn.com/problems/next-permutation
 *
 * @author godfrey
 * @since 2020-11-04
 */
@DisplayName("下一个排列")
public class NextPermutation extends BaseTest {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments((Object) new int[]{1, 2, 3}),
                Arguments.arguments((Object) new int[]{3, 2, 1}),
                Arguments.arguments((Object) new int[]{1, 1, 5}),
                Arguments.arguments((Object) new int[]{1, 3, 2}),
                Arguments.arguments((Object) new int[]{2, 3, 1}),
                Arguments.arguments((Object) new int[]{4, 2, 0, 2, 3, 2, 0}),
                Arguments.arguments((Object) new int[]{1, 2})
        );
    }

    @DisplayName("时间复杂度O(n)，空间复杂度O(1)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void nextPermutation(int[] nums) {
        final int len = nums.length;
        for (int i = len - 1; i > 0; --i) {
            //从右向左，先找出索引 i 满足 nums[i-1] < nums[i]，
            if (nums[i] > nums[i - 1]) {
                //排序
                Arrays.sort(nums, i, len);
                //遍历{i..len-1}找到第一个比num[i-1]大的数，交换num[i-1]和num[j]
                for (int j = i; j < len; ++j) {
                    if (nums[j] > nums[i - 1]) {
                        int temp = nums[j];
                        nums[j] = nums[i - 1];
                        nums[i - 1] = temp;
                        //交换直接结束
                        return;
                    }
                }
            }
        }
        //未找到，表面是没有下一个更大的序列了
        Arrays.sort(nums);
    }
}

